#权重为0或1的图的最短路径算法

from collections import deque

def dist01(graph, weight, source=0, target=None):
    """权重为0或1的图的最短路径算法
        :param graph：list(list)或list(dict)格式的定向图
        :param weight：矩阵或邻接字典
        :param int source：节点
        :param target：目标点，找到则停止遍历
        :返回：距离表，前置表
        :复杂度:`O(|V|+|E|)`
    """
    n = len(graph) #节点个数
    dist = [float('inf')] * n #回到起始点的距离
    prec = [None] * n #节点的前置节点
    black = [False] * n #已经遍历过的节点
    dist[source] = 0 #起始点到起始点距离为0
    gray = deque([source]) #双向队列
    while gray:
        node = gray.pop() #从后取出
        if black[node]: #已经标黑，则跳过
            continue
        black[node] = True #开始(被)遍历则标黑
        if node == target: #找到目标点，则停止遍历
            break
        for neighbor in graph[node]: #点的后继路径
            ell = dist[node] + weight[node][neighbor] #后继点距离
            #如果neighbor已经被遍历过或者其他路径距离小于这个路径距离，跳过
            if black[neighbor] or dist[neighbor] <= ell: 
                continue
            dist[neighbor] = ell #更新距离
            prec[neighbor] = node #更新前者节点
            if weight[node][neighbor] == 0:
                gray.append(neighbor) #如果权重为0，提高遍历优先
            else:
                gray.appendleft(neighbor) #降低遍历优先
    return dist, prec
